/* Create directed acyclic graph layout using Hasse diagram */

#include <algorithm>

#include <gtkmm/widget.h>

#include <memchart/types.hpp>

#include "chart_box.hpp"

#include "memory_chart.hpp"

namespace memchart
{
	using std::deque;

	namespace
	{
		struct compare_boxes
		{
			bool operator () (const box_iter & x, const box_iter & y) const
			{
				const chart_box & a = x->second;
				const chart_box & b = y->second;

				return (a.child_count + a.lparent_count + a.rparent_count) >
					(b.child_count + b.lparent_count + b.rparent_count);
			}

			box_map & boxes;

			compare_boxes (box_map & boxes)
				: boxes(boxes)
			{ }
		};
	}

	void MemoryChart::layout_dag ()
	{
		for (box_iter v = boxes.begin(); v != boxes.end(); ++v)
		{
			chart_box & box = v->second;

			box.lparent_count = box.rparent_count = box.child_count = 0;

			for (edge_iter e = box.edges.begin(); e != box.edges.end(); ++e)
			{
				box_iter v2 = boxes.find(*e);
				if (v2 != boxes.end())
					box.child_count++;
			}
		}

		vector<deque<box_iter> > rows;
		typedef deque<box_iter>::iterator row_iter;

		vector<box_iter> cur_row;
		size_t level = 0;

		for (vector<box_iter>::iterator v = torder.begin(); ; ++v)
		{
			if (v == torder.end() || (*v)->second.level != level)
			{
				rows.push_back(deque<box_iter>());

				std::sort(cur_row.begin(), cur_row.end(), compare_boxes(boxes));

				for (size_t i = 0; i < cur_row.size(); i++)
				{
					chart_box & cur = cur_row[i]->second;

					if (cur.lparent_count > cur.rparent_count)
						rows.rbegin()->push_front(cur_row[i]);
					else
						rows.rbegin()->push_back(cur_row[i]);
				}

				size_t i = 0;
				for (row_iter it = rows.rbegin()->begin();
					it != rows.rbegin()->end(); ++it, ++i)
				{
					chart_box & cur = (*it)->second;

					for (edge_iter e = cur.edges.begin();
						e != cur.edges.end(); ++e)
					{
						box_iter v2 = boxes.find(*e);
						if (v2 != boxes.end())
						{
							i < rows.rbegin()->size() / 2
								? v2->second.lparent_count++
								: v2->second.rparent_count++;
						}
					}
				}

				if (v == torder.end())
					break;
				else
				{
					cur_row.clear();
					level++;
				}
			}
			cur_row.push_back(*v);
		}

		/* Compute widths of all rows for centering */
		vector<int> row_widths;
		row_widths.reserve(rows.size());
		for (size_t i = 0; i < rows.size(); i++)
		{
			int width = 0;
			for (row_iter it = rows[i].begin(); it != rows[i].end(); ++it)
				width += (*it)->second.widget->get_width() + hspacing;
			row_widths.push_back(width - hspacing);
		}
		int max_width = *std::max_element(row_widths.begin(), row_widths.end());

		/* Go through each row and position boxes */
		int y = 0;
		for (size_t i = 0; i < rows.size(); i++)
		{
			int x = (max_width - row_widths[i]) / 2;
			int max_height = 0;
			for (row_iter it = rows[i].begin(); it != rows[i].end(); ++it)
			{
				Gtk::Widget & widget = *(*it)->second.widget;

				move(widget, x, y);
				x += widget.get_height() + hspacing;
				max_height = std::max(max_height, widget.get_height());
			}
			y += max_height + vspacing;
		}
		y -= vspacing;

		set_size_request(max_width, y);
	}
}
